package com.计算整数包含多少个1;

public class Demo {
	
	//位移法
	//思路：既然输入n是uint32，每次取n的最低位，判断是不是1，位移32次，循环判断即可。
	public static int remove(int n){
		int result = 0;
		int i = 0;
		do{
		    if ((n&1) == 1){
		       result++;
		    }
		    n>>= 1;
		    i++;
		} while(i < 32);
		
		return result;
	}
	
	//二、求与法
	//观察一下n与n-1这两个数的二进制表示：
	//最末位一个1会变成0
	//最末位一个1之后的0会全部变成1
	//其他位相同
	//栗子：
	//        x = 1011 0000
	//       x-1= 1010 1111
	//x & (x-1) = 1010 0000
	//于是，n&(n-1)这个操作，可以起到“消除最后一个1”的功效。
	//思路：逐步通过n&(n-1)，来消除n末尾的1，消除了多少次，就有多少个1。
	public static int and(int n){
		int result = 0;
		while(n > 0){
			n = n&(n-1);
			result++;
		}
		return result;
	}
	
	public static void main(String[] args) {
		System.out.println(remove(58585858));
		System.out.println(and(58585858));
	}

}
